package LeetCode;

import java.util.Arrays;
import java.util.List;

//
// Created by ✎﹏ℳ๓独赏☆独醉 on 2024/5/9.
//
//https://leetcode.cn/problems/next-permutation/description/
public class 下一个排列 {
    public static void main(String[] args) {
        int[] nums = {2,3,1};
        nextPermutation(nums);
        System.out.println(Arrays.toString(nums));
    }

    private static void nextPermutation(int[] nums) {
        if(nums.length == 0)return;
        int target = -1;
        for(int i = nums.length-1;i>0;i--){
            if(nums[i] > nums[i-1]){
                target = i-1;
                break;
            }
        }
        if(target == -1){
            Arrays.sort(nums);
            return;
        }
        int tempIndex = -1;
        for(int i = nums.length - 1;i > target;i--){
            if(nums[target] < nums[i]){
                tempIndex = i;
                break;
            }
        }
        int tempNums = nums[tempIndex];
        nums[tempIndex] = nums[target];
        nums[target] = tempNums;
        int[] tempArr = new int[nums.length - target -1];
        System.arraycopy(nums, target + 1, tempArr, 0, tempArr.length);
        Arrays.sort(tempArr);
        System.arraycopy(tempArr, 0, nums, target + 1, tempArr.length);
    }


//    public static void nextPermutation(int[] nums) {
//        if(nums.length == 0)return;
//        int i,j = 0;
//        flag:for ( i = nums.length-1; i > 0 ; i--) {
//            for (j = i-1; j >= 0 ; j--) {
//                if(nums[i] > nums[j]){
//                    break flag;
//                }
//            }
//        }
//        if(j == -1){
//            Arrays.sort(nums);
//            return;
//        }
//        if(j+1 != i){
//            int temp = nums[i];
//            nums[i] = nums[j];
//            nums[j] = temp;
//            int[] tempArr = new int[nums.length - j - 1];
//            System.arraycopy(nums,j+1,tempArr,0,tempArr.length);
//            Arrays.sort(tempArr);
//            System.arraycopy(tempArr,0,nums,j+1,tempArr.length);
//        }else {
//            int temp = nums[i];
//            nums[i] = nums[j];
//            nums[j] = temp;
//            int[] tempArr = new int[nums.length - j -1];
//            System.arraycopy(nums,j+1,tempArr,0,tempArr.length);
//            Arrays.sort(tempArr);
//            System.arraycopy(tempArr,0,nums,j+1,tempArr.length);
////        }

//        int[] tempArr = new int[nums.length - i];
//        System.arraycopy(nums,i,tempArr,0,nums.length - i);
//        System.arraycopy(nums,j,nums,nums.length - j,i-j);
//        System.arraycopy(tempArr,0,nums,j,tempArr.length);
//    }
}
